<!--
 * @Descripttion: 
 * @version: 
 * @Author: 尹鹏孝
 * @Date: 2021-12-20 09:16:52
 * @LastEditors: 尹鹏孝
 * @LastEditTime: 2021-12-20 09:42:52
-->
<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>递归中带有回溯</title>
</head>

<body>
    <script>
        // 回溯就隐藏在traversal(cur -> left, path + "->", result);中的 path + "->"。 每次函数调用完，path依然是没有加上"->" 的，这就是回溯了
        /**
         * @name: TreeNode
         * @msg: 二叉树
         * @param {Object|number} val：值
         * @param {Object|null} left：左树
         * @param {Object|null} right：右树
         * @return {Object|null} null：返回值
         */
        function TreeNode(val, left, right) {
            this.val = val || 0;
            this.left = left || null;
            this.right = right || null;
        }
        /**
         * @name: isSameTree
         * @msg: 是否相同的树
         * @param {TreeNode} p
         * @param {TreeNode} q
         * @return {Boolean}
         */
        function isSameTree(p, q) {
            if (p === null && q === null) {
                return true;
            } else if (p === null || q === null) {
                return false;
            } else if (p.val != q.val) {
                return false;
            } else {
                return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
            }
        }
        /**
         * @name: binaryTreePath
         * @msg: 二叉树路径回溯法
         * @param {NodeTree} root
         * @return {string[]}
         */
        var binaryTreePath = function (root) {
            /**
             * @name: getPath
             * @msg: 递归回溯求路径
             * @param {TreeNode,array,array} root, path, result
             * @return {Array}result
             */
            const getPath = (root, path, result) => {
                path.push(root.val);
                if (root.left === null && root.right === null) {
                    let n = path.length;
                    let str = '';
                    for (let i = 0; i < n - 1; i++) {
                        str += path[i] + '->';
                    }
                    str += path[n - 1];
                    result.push(str);
                }
                if (root.left != null) {
                    getPath(root.left, path, result);
                    path.pop();// 回溯
                }

                if (root.right != null) {
                    getPath(root.right, path, result);
                    path.pop();// 回溯
                }

            }

            if (root === null) {
                return [];
            }
            let result = [];
            let path = [];
            getPath(root, path, result);
        }
    </script>
</body>

</html>